package org.moonshiner.alg.quicksort;

import org.moonshiner.alg.util.StdRandom;

public class Quick {

	public static void sort(Comparable[] a) {
		StdRandom.shuffle(a);
		sort(a, 0, a.length - 1);
	}

	private static void sort(Comparable[] a, int low, int high) {
		if (high <= low) {
			return;
		}
		int j = partition(a, low, high);
		sort(a, low, j - 1);
		sort(a, j + 1, high);
	}

	private static int partition(Comparable[] a, int low, int high) {

		int i = low;
		int j = high + 1;
		Comparable v = a[low];
		while (true) {
			while (less(a[++i], v)) {
				if (i == high)
					break;
			}
			while (less(v, a[--j])) {
				if (j == low)
					break;
			}
			if (i >= j)
				break;

			exch(a, i, j);
		}
		exch(a, low, j);
		return j;
	}

	private static boolean less(Comparable v, Comparable w) {
		return v.compareTo(w) < 0;
	}

	private static void exch(Object[] a, int i, int j) {
		Object swap = a[i];
		a[i] = a[j];
		a[j] = swap;
	}

}
